package stringFind

import "math"

func BMSearch(main, pattern string) int {
	if len(main) == 0 || len(pattern) == 0 || len(main) < len(pattern) {
		return -1
	}

	// 给模式串中每一个字符建立索引
	bc := GenerateBC(pattern)
	// 计算好后缀数组
	suffix, prefix := GenerateGS(pattern)

	n := len(main)
	m := len(pattern)

	step := 1 // 每次匹配过程中模式串往后滑动的距离
	for i := 0; i <= n-m; i += step {
		subStr := main[i : i+m] // 待匹配的主串

		// 在主串中查找坏字符位置
		// k是坏字符在模式串中的位置, j是坏字符在subStr中的位置
		k, j := findBadChar(subStr, pattern, bc)

		// j ==-1说明没有坏字符，匹配完成
		if j == -1 {
			return i
		}
		// 通过坏字符计算出来的滑动距离
		stepForBC := j - k // stepForBC要大于0才有效

		// 通过好后缀规则计算出的滑动距离
		stepForGS := -1
		// j==m-1时说明没有好后缀
		if j < m-1 {
			stepForGS = moveByGS(m, j, suffix, prefix)
		}

		// k是怀字符在模式串中的索引位置

		// 模式串滑动的距离是坏字符和好后缀规则中最大的那个
		step = int(math.Max(float64(stepForBC), float64(stepForGS)))
	}

	return -1
}

func moveByGS(patternLen, badCharIndexStart int, suffix []int, prefix []bool) int {
	// 计算好后缀的长度
	k := patternLen - badCharIndexStart - 1
	// 好后缀子串在模式串中找得到
	// suffix中已经包含了好后缀在模式串中是否存在（除好后缀本身外）
	if suffix[k] != -1 {
		return badCharIndexStart - suffix[k] + 1
	}
	// 好后缀和好后缀子串是不同的  cab是好后缀，b ab cab这些都是好后缀子串 ,好后缀一最多只有一个，好后缀子串可以有多个
	// 好后缀是好后缀子串中的一个，且是长度最长的一个
	// 好后缀在模式串中找不到
	// 查找好后缀子串是否跟前缀子串匹配
	for i := patternLen - 1; i > badCharIndexStart+1; i-- {
		if prefix[i] {
			return i
		}
	}

	// 好后缀既没有出现在模式串中，也没有好后缀子串跟模式串前缀子串匹配
	return patternLen
}

// 查找坏字符在模式串中的位置
func findBadChar(subStr, pattern string, bc []int) (int, int) {
	j := -1
	k := -1

	badChar := rune(0)
	// 从后往前比较，找出第一个坏字符的位置
	for i := len(subStr) - 1; i >= 0; i-- {
		// 出现坏字符
		if subStr[i] != pattern[i] {
			j = i
			badChar = rune(subStr[i]) // 坏字符的rune值
			break                     // 跳出循环
		}
	}

	// 如果坏字符存在，则找到他在模式串中的索引位置
	if j > 0 {
		k = bc[rune(badChar)]
	}
	return k, j
}

func GenerateBC(pattern string) []int {
	bc := make([]int, 256)

	for i := range bc {
		bc[i] = -1
	}
	// 计算字符 最后一次(每个字符c都可能重复,只记录最靠后的一次) 出现在模式串中的索引位置
	// 数组下标位字符c的rune值，也是int值
	for i, c := range pattern {
		bc[rune(c)] = i
	}
	return bc
}

func GenerateGS(pattern string) ([]int, []bool) {
	m := len(pattern)

	// 后缀子串出现位置数组和后缀子串是否匹配前缀子串数组长度为m（之所以不等于m-1是因为0这个位置是空缺的）
	suffix := make([]int, m)  // 计算模式串中后缀子串在模式串的起始位置
	prefix := make([]bool, m) // 如果模式串中的后缀子串在模式串的前缀子串中出现则为true

	// 初始化
	for i := 0; i <= m-1; i++ {
		suffix[i] = -1
		prefix[i] = false
	}

	// 遍历模式串，并搜索前缀子串 i只能读到m-2是因为前缀子串最长为模式串长度-1（前缀子串的定义）
	for i := 0; i <= m-2; i++ {
		j := i // j控制前缀子串
		k := 0 // k控制后缀子串
		// 扫描每一个后缀子串
		for j >= 0 && pattern[j] == pattern[m-1-k] {
			k++
			// 记录后缀子串在模式串中的起始位置
			suffix[k] = j
			j--
		}
		if j == -1 {
			// 记录后缀子串是否和前缀子串匹配
			prefix[k] = true
		}
	}
	// 假如模式串是: c a b c a b  长度为6
	// 下标位置:    0 1 2 3 4 5
	// 后缀子串以及长度 <--
	// 其实如果知道好后缀只是模式串的一部分，后缀子串是不需要全部计算的,只需要小于等于好后缀就可以了（但是我们是提前计算好，怎么可能知道每次匹配时好后缀是多少）
	//     b  1
	//    ab  2
	//   cab  3
	//  bcab  4
	// abcab  5

	// 前缀子串以及长度
	//     c  1
	//    ca  2
	//   cab  3
	//  cabc  4
	// cabca  5

	// suffix[1] == 2 // 子串b在模式串的起始位置为2 （除开后缀子串本身）
	// suffix[2] == 1 // 子串ab在模式串的起始位置为1 （除开后缀子串本身）
	// suffix[3] == 0  //子串cab在模式串的起始位置为0 （除开后缀子串本身）
	// suffix[4] == -1  //子串bcab在模式串中找不到 （除开后缀子串本身）
	// suffix[5] == -1 //子串abcab在模式串中找不到（除开后缀子串本身）

	// prefix[1] ==false // 子串b和前缀子串都不匹配
	// prefix[2] == false // 子串ab和前缀子串都不匹配
	// prefix[3] == true // 子串cab和前缀子串cab匹配
	// prefix[4] == false // 子串bcab和前缀子串不匹配
	// prefix[5] == false // 子串abcab和前缀子串不匹配
	return suffix, prefix
}
